package leetcode.code2080;

import java.util.HashMap;
import java.util.Map;

import leetcode.helper.HelpDebug;

public class RangeFreqQuery {

	class Node {
		private int Start;
		private int End;
		private int Mid;
		private Node Left;
		private Node Right;
		private Map<Integer, Integer> hash;

		public Node(int start, int end) {
			this.Start = start;
			this.End = end;
			this.Mid = ((end - start) >> 1) + start;
			this.hash = new HashMap<>();
		}

		private Node getLeft() {
			if (this.Left == null) {
				this.Left = new Node(this.Start, this.Mid);
			}
			return this.Left;
		}

		private Node getRight() {
			if (this.Right == null) {
				this.Right = new Node(this.Mid + 1, this.End);
			}
			return this.Right;
		}

		public void add(int index, int num) {
			if (this.Start == this.End && this.Start == index) {
				this.hash.put(num, 1);
				return;
			}
			this.hash.put(num, this.hash.getOrDefault(num, 0) + 1);
			if (index <= Mid) {
				this.getLeft().add(index, num);
			} else if (index > Mid) {
				this.getRight().add(index, num);
			}
		}

		public int query(int l, int r, int num) {
			if (this.Start == l && this.End == r) {
				return this.hash.getOrDefault(num, 0);
			} else if (r <= this.Mid) {
				return this.getLeft().query(l, r, num);
			} else if (l > this.Mid) {
				return this.getRight().query(l, r, num);
			} else {
				int ans = this.getLeft().query(l, this.Mid, num);
				ans += this.getRight().query(this.Mid + 1, r, num);
				return ans;
			}
		}
	}

	private Node root;

	public RangeFreqQuery(int[] arr) {
		int len = arr.length;
		root = new Node(0, len - 1);
		for (int i = 0; i < len; i++) {
			root.add(i, arr[i]);
		}
	}

	public int query(int left, int right, int value) {
		return root.query(left, right, value);
	}

	public static void main(String[] args) {
		RangeFreqQuery rangeFreqQuery = new RangeFreqQuery(
				HelpDebug.str2array3("[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]"));
		int a = rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
		int b = rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。
		System.out.println((a == 1) + " " + (b == 2));
	}

}
